//
// Created by Cammy on 2024/4/29.
//
#include "Tree.h"


void PrevOrder(BTNode *root) {
    if (root == NULL) {
        printf("NULL ");
        return;
    }
    printf("%c ", root->data);
    PrevOrder(root->left);
    PrevOrder(root->right);
}

void InOrder(BTNode *root) {
    if (root == NULL) {
        printf("NULL ");
        return;
    }
    InOrder(root->left);
    printf("%c ", root->data);
    InOrder(root->right);
}

void PostOrder(BTNode *root) {
    if (root == NULL) {
        printf("NULL ");
        return;
    }
    PostOrder(root->left);
    PrevOrder(root->right);
    printf("%c ", root->data);
}

int TreeSize(BTNode *root) {
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

int TreeLeafSize(BTNode *root) {
    if (root == NULL)
        return 0;

    if (root->left == NULL && root->right == NULL)
        return 1;

    return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

void LevelOrder(BTNode *root) {
    Queue q;
    QueueInit(&q);
    if (root)
        QueuePush(&q, root);

    while (!QueueEmpty(&q)) {
        BTNode *front = QueueFront(&q);
        QueuePop(&q);
        printf("%c ", front->data);

        if (front->left) {
            QueuePush(&q, front->left);
        }

        if (front->right) {
            QueuePush(&q, front->right);
        }
    };

    printf("\n");

    QueueDestroy(&q);
}

void DestroyTree(BTNode *root) {
    if (root == NULL)
        return;

    DestroyTree(root->left);
    DestroyTree(root->right);

    free(root);
    root = NULL;
}

// --------------------------------------------------------------------------------------------------------------

void QueueInit(struct Queue *pq) {
    assert(pq);
    pq->head = pq->tail = NULL;
}

void QueueDestroy(Queue *pq) {
    assert(pq);
    QNode *cur = pq->head;
    while (cur != NULL) {
        QNode *next = cur->next;
        free(cur);
        cur = next;
    }
}

// 队尾入
void QueuePush(Queue *pq, QDataType x) {
    assert(pq);
    QNode *newnode = (QNode *) malloc(sizeof(QNode));
    if (newnode == NULL) {
        printf("malloc fail...\n");
        exit(-1);
    }

    newnode->data = x;
    newnode->next = NULL;

    if (pq->head == NULL) {
        pq->head = pq->tail = newnode;
    } else {
        pq->tail->next = newnode;
//        pq->tail=pq->tail->next;
        pq->tail = newnode;
    }
}

// 队头出
void QueuePop(Queue *pq) {
    assert(pq);
    assert(pq->head);

//    if (pq->head == pq->tail) {
    if (pq->head->next == NULL) {
        free(pq->head);
        pq->head = pq->tail = NULL;
    } else {
        QNode *headNext = pq->head->next;
        free(pq->head);
        pq->head = headNext;
    }
}

//取队头
QDataType QueueFront(Queue *pq) {
    assert(pq);
    return pq->head->data;
}

//取队尾
QDataType QueueBack(Queue *pq) {
    assert(pq);
    return pq->tail->data;
}

int QueueSize(Queue *pq) {
    assert(pq);
    int size = 0;
    QNode *cur = pq->head;
    while (cur != NULL) {
        size++;
        cur = cur->next;
    }
    return size;
}

bool QueueEmpty(Queue *pq) {
    assert(pq);
    return pq->head == NULL;
}